#include <iostream>     // std::cout, std::cin
#include <algorithm>    // std::sort
#include <vector>       // std::vector
#include <list>
#include <set>
#include "Ej3.h"
#include <queue>

Grafo::Grafo(int _n, int _m, int _k): n(_n), m(_m), k(_k)
{
  //matriz_ad.resize(n);
  for (int i=0; i<n ; i++){
	matriz_ad.push_back(vector<float>(n,-1));
  }
    
}

Nodo::Nodo(int _id): id(_id)
{
  grado = 0;
  pesos_ady = 0;
  id_particion = -1;
}

Vertice::Vertice(int _id_u, int _id_v, float _w): id_u(_id_u), id_v(_id_v), w(_w){}

Particion::Particion(int _id): id(_id)
{
  peso = 0;
 }

Resultado::Resultado(int _k): k(_k)
{
  pesoTotal = 0;
  //particiones.resize(k);
  for(int i=0; i<k; i++){
	particiones.push_back(Particion(i));
  }
}

void imprimir_resultado(vector <Nodo> &nodos){
	cout << "el resultado es el siguiente: " << endl;
	for (unsigned int i=0; i < nodos.size(); i++){
		cout << nodos[i].id_particion +1 << " " ;
	}
	cout << endl;
}

void goloso(Grafo &g, vector<Nodo> &nodos, priority_queue<Vertice> &vertices, Resultado &res){
	cout << "entre al goloso" << endl;
	int id_n1, id_n2;
	float w;
	Vertice v(0,0,0);
	int part_actual = 0;
	if (!vertices.empty()){
		cout << "entre al primer if" << endl;
		v = vertices.top();
		vertices.pop();
		id_n1 = v.id_u;
		id_n2 = v.id_v;
		w = v.w;
		res.particiones[part_actual].id_nodos.insert(id_n1);
		nodos[id_n1].id_particion = part_actual;
		//g[id_n1][id_n2] = -1;
		part_actual = (part_actual+1) % res.k;
		res.particiones[part_actual].id_nodos.insert(id_n2);
		nodos[id_n2].id_particion = part_actual;
		//g[id_n2][id_n1] = -1;
	}
	
	while(!vertices.empty()){
		v = vertices.top();
		vertices.pop();
		id_n1 = v.id_u;
		id_n2 = v.id_v;
		w = v.w;
		//si todavia no pertenece a alguna particion lo agrego a alguna
		if (nodos[id_n1].id_particion==-1){
			part_actual = (part_actual+1) % res.k; //avanzo una particion
			res.particiones[part_actual].id_nodos.insert(id_n1);
			nodos[id_n1].id_particion = part_actual;
			//g[id_n1][id_n2] = -1;
			//part_actual = (part_actual+1) % res.k;
			//si al agregar el nodo adyacente esta en la misma particion entonces agrego el peso de la arista a la particion
			if (nodos[id_n2].id_particion==part_actual){
				res.particiones[part_actual].peso += w;
			}//si el nodo adyacente no pertenece a la particion actual puede pertenecer a otra o a ninguna
			else{
				//si no pertenece a ninguna lo agrego a alguna
				if(nodos[id_n2].id_particion==-1){
					part_actual = (part_actual+1) % res.k; //me muevo en 1 en los conjuntos de particiones
					res.particiones[part_actual].id_nodos.insert(id_n2);
					nodos[id_n2].id_particion = part_actual;
					//g[id_n2][id_n1] = -1;
					//todavia puede pasar que al agregar el segundo coincida justo con la particion dl primero
					if (nodos[id_n1].id_particion==part_actual){
						res.particiones[part_actual].peso += w;
					}
				}
			}
		}
		else{
			//si el nodo actual ya pertenece a alguna particion solo queda agregar el segundo
			//primero tengo que saber si no tiene particion (aunque al ser una arista nueva no puede pasar que los dos ya tengan particion, seria lo mismo que considerar el caso en que ya exista la arista actual)
			if (nodos[id_n2].id_particion==-1){
				part_actual = (part_actual+1) % res.k; //me muevo en 1 en los conjuntos de particiones
				res.particiones[part_actual].id_nodos.insert(id_n2);
				nodos[id_n2].id_particion = part_actual;
			}
			else{
				//si justo coincide con la particion del primer nodo
				if (nodos[id_n1].id_particion==part_actual){
					res.particiones[part_actual].peso += w;
				}
			}
		}
		
	}
	
	//actualizo la suma total de todas las particones
	for (int i=0; i<res.k; i++){
		res.pesoTotal += res.particiones[i].peso;
	}

}

void ej3(){
	
int n, m, k, n1, n2;
float w;
cin >> n;
cin >> m;
cin >> k;

Grafo g(n, m, k);	
vector <Nodo> nodos;
priority_queue <Vertice> vertices;

	for (int i=0; i<n ; i++){
	nodos.push_back(Nodo(i));
	}
/*
cout << "la matriz del grafo cuenta con la siguiente info:" << endl;
for (int i=0; i< n; i++){
	for (int j=0; j< n ; j++){
	cout << "| " << g.matriz_ad[i][j] << " |";
	}
	cout << endl;
}
	*/
	
	cout << "los nodos quedan definidos" << endl;
	for (int j=0; j< n ; j++){
	cout << "| " << nodos[j].id << " |";
	}
	cout << endl;
	
	
	for (int i=0; i<m ; i++){
	cin >> n1;
	cin >> n2;
	cin >> w;
	g.matriz_ad[n1-1][n2-1] = w;
	g.matriz_ad[n2-1][n1-1] = w;
	nodos[n1-1].pesos_ady += w;
	nodos[n1-1].grado += 1;
	nodos[n2-1].pesos_ady += w;
	nodos[n2-1].grado += 1;
	vertices.push(Vertice(n1-1,n2-1,w));
	}
	
Resultado res(k);
goloso(g, nodos, vertices, res);
imprimir_resultado(nodos);
}




int main()
{
  while(cin.peek() != 48) {
    ej3();
    cin.get();
  }
   return 0;
}
